9755. Молчание ламп

Во-первых, для тех, кто никогда не видел лампу, представим, что это прямоугольный параллелепипед (коробка с прямоугольными гранями), сделанный из стекла и заполненный газом. Все стороны лампы имеют целочисленные длины.

Однажды наш преподаватель был осуждён за разрушение ламп на улице. Он, должно быть, немного сошел с ума, так как думал, что некоторые из ламп кричали на него пронзительными голосами.

В его красивом уме он следовал странной закономерности. Он признавал и разрушал только те лампы, которые не имели квадратной грани и чей объём не превышал фиксированное значение. Позже, во время сеанса с его доктором Кларисой, он сказал, что очень боится больших объектов и объектов со слишком правильной формой.

Ваша задача – посчитать все возможные формы ламп, подходящие под условия преподавателя.

Вход. Первая строка содержит число тестов t (1 ≤ t ≤ 10⁵). Каждая из следующих t строк содержит одно целое число n (1 ≤ n ≤ 10⁶), максимальный распознаваемый объём лампы.

Выход. Для каждого теста выведите количество различных форм ламп, которые могли быть разрушены в приступе ярости.

Пример входа	Пример выхода
5 5 6 10 30 666	0 1 3 26 2406

РЕШЕНИЕ

перебор + префиксные суммы

Анализ алгоритма

Представим лампу в виде параллелепипеда размером x * y * z. Нас интересуют только лампы без квадратных граней, значит x < y < z. При помощи трех вложенных циклов переберем все тройки (x, y, z) такие что x * y * z ≤ 10⁶.

Обнулим массив res. Для каждой такой тройки (x, y, z) отметим res[x * y * z] = 1. Далее на массиве res посчитаем префиксные суммы и занесем их в тот же массив res.

Тогда если n – максимальный распознаваемый объём лампы, то количество различных форм ламп равно res[n].

Пример

Рассмотрим какие размеры могут иметь лампы. Наименьший размер лампы равен 1 * 2 * 3 = 6. Искомыми размерами ламп без квадратных граней, например, будут:

Тогда после перебора троек массив res будет иметь вид:

После вычисления префиксных сумм:

Реализация алгоритма

Объявим рабочий массив.

#define MAX 1000001

int res[MAX];

Перебором находим все тройки (x, y, z) такие что x * y * z ≤ 10⁶.

for (i = 1; i < MAX; i++)

for (j = i + 1; i * j < MAX; j++)

for (k = j + 1; i * j * k < MAX; k++)

res[i * j * k]++;

Вычисляем префиксные суммы для массива res.

for (i = 1; i <= MAX; i++)

res[i] = res[i - 1] + res[i];

Читаем количество тестов t.

scanf("%d", &t);

while (t--)

{

Для каждого входного значения n выводим res[n].

scanf("%d", &n);

printf("%d\n", res[n]);

}